package com.d0717;

import java.util.Arrays;

/**
 * @author mwl
 * @date 2018-07-17
 * <p>
 * https://leetcode.com/problems/two-sum/description/
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * <p>
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 * <p>
 * Example:
 * <p>
 * Given nums = [2, 7, 11, 15], target = 9,
 * <p>
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 * </p>
 **/
public class TowNumber {
    public static void main(String[] args) {

        TowNumber towNumber = new TowNumber();
        int[] nums = new int[4];
        //        for (int i = 0; i < 10; i++) {
        //            nums[i] = new Random().nextInt(1000);
        //        }
        nums[0] = -3;
        nums[1] = 4;
        nums[2] = 3;
        nums[3] = 9;
        int[] result2 = towNumber.twoSum(nums, 0);
        if (result2 != null) {
            System.out.println(Arrays.toString(result2));
        }
        System.out.println(Arrays.toString(nums));
        //        for (int target = 700; target < 1000; target++) {
        //            int[] result = towNumber.twoSum(nums, target);
        //            if (result != null) {
        //                System.out.println(target);
        //                System.out.println(Arrays.toString(result));
        //                break;
        //            }
        //        }
        //        System.out.println(Arrays.toString(nums));

    }

    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return null;
        }
        int[] num2 = Arrays.copyOf(nums, nums.length);
        Arrays.sort(num2);
        int[] result = null;

        int left = 0;
        int right = num2.length - 1;
        for (int i = left; i < right; i++) {
            int target2 = target - num2[i];
            int right2 = binarySearch(num2, i + 1, right, target2);
            if (right2 >= 0 && right2 != i && num2[right2] == target2) {
                result = new int[2];
                result[0] = i;
                result[1] = right2;
                break;
            }
        }
        if (result != null) {
            int[] result2 = new int[2];
            result2[0] = -1;
            result2[1] = -1;
            for (int i = 0; i < nums.length; i++) {
                if (num2[result[0]] == nums[i] && result2[0] < 0) {
                    result2[0] = i;
                } else if (num2[result[1]] == nums[i] && result2[1] < 0) {
                    result2[1] = i;
                }
                if (result2[0] > -1 && result2[1] > -1) {
                    return result2;
                }
            }
        }
        return null;
    }

    /**
     * 查找<=key 最接近的数字下标
     *
     * @param a
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return
     */
    public int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid; // key found
            }
        }
        return low - 1;  // key not found.
    }
}
